package demo4;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-09-01
 * Time: 9:24
 */
public class TestDemo {

    //给你一组货币,该货币数组所有的货币都不一样,如果面值一样也认为是不一样的货币,求出
    //能够组成aim有多少种方法数??
    //比如[1,1,1] aim = 2 组成2的方法数有3种方法
    public static int ways1(int[] arr,int aim){
        return process(arr,0,aim);
    }

    //从index开始往后面能组成rest的方法数有多少种
    public static int process(int[] arr,int index,int rest){
        if(rest<0){
            //如果剩余的钱数<0,那证明没有方法了
            return 0;
        }
        if(index == arr.length){
            //如果index越界,看看剩下钱数是否为0
            //如果为0那证明有1种方法数,否则没有方法数
            return rest == 0 ? 1 : 0;
        }
        //接下来的情况是一种是要index位置的钱,一种是不要index位置的钱.
        return process(arr,index+1,rest-arr[index])
                + process(arr,index+1,rest);
    }

    public static int waysDp(int[] arr,int aim){
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;//当在第N行的时候只有0位置是1
        for(int index = N-1;index>=0;index--){
            for(int rest =0;rest<=aim;++rest){
                dp[index][rest] = dp[index+1][rest];
                if(rest-arr[index]>=0){
                    dp[index][rest] += dp[index+1][rest-arr[index]];
                }
            }
        }
        return dp[0][aim];
    }


    public static void main(String[] args) {
        int[] arr = {1,1,1};
        System.out.println(ways1(arr, 2));
        System.out.println(waysDp(arr, 2));
    }
}
